package sortAlgorithm;

/**
 * MergeSort
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: 归并排序
 * @date 2021/6/7
 **/
public class MergeSort {
    public static void mergeSort(int[] nums, int length) {
        if (length <= 1) {
            return;
        }
        mergeSort(nums, 0, length - 1);
    }

    private static void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int p = (start + end) / 2;
        //不断将数组划分成小区间
        mergeSort(nums, start, p);
        mergeSort(nums, p + 1, end);
        merge(nums, start, p, p + 1, end);
    }

    /**
     * @param nums   操作的数组
     * @param start1 第一部分待合并数组的起始下标
     * @param end1   第一部分待合并数组的终止下标
     * @param start2 第二部分待合并数组的起始下标
     * @param end2   第二部分待合并数组的起始下标
     */
    private static void merge(int[] nums, int start1, int end1, int start2, int end2) {
        int[] tmpArray = new int[end2 - start1 + 1];
        int i = start1, j = start2, k = 0;
        while (i <= end1 && j <= end2) {
            if (nums[i] <= nums[j]) {
                tmpArray[k++] = nums[i++];
            } else {
                tmpArray[k++] = nums[j++];
            }
        }
        while (i <= end1) {
            tmpArray[k++] = nums[i++];
        }
        while (j <= end2) {
            tmpArray[k++] = nums[j++];
        }
        k = 0;
        for (int m = start1; m <= end2; ++m) {
            nums[m] = tmpArray[k++];
        }
    }
}
